package practice;

import java.util.Stack;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName Tree.java
 * @Description TODO
 * @createTime 2020年09月24日 09:15:00
 */
public class Tree {
	public static void main(String[] args) {
		PracticeTreeNode node = initBinaryTree();
		nonRecursiveAfterForeachBinaryTree(node);
	}

	public static PracticeTreeNode initBinaryTree() {
		PracticeTreeNode root = new PracticeTreeNode(4);
		root.left = new PracticeTreeNode(2);
		root.right = new PracticeTreeNode(6);

		root.left.left = new PracticeTreeNode(1);
		root.left.right = new PracticeTreeNode(3);

		root.right.left = new PracticeTreeNode(5);
		root.right.right = new PracticeTreeNode(7);
		root.right.right.left = new PracticeTreeNode(8);

		return root;
	}

	public static void recursiveFirstForeachBinaryTree(PracticeTreeNode root) {
		if (root == null) {
			return;
		}
		System.out.println(root.val);
		if (root.left != null) {
			recursiveFirstForeachBinaryTree(root.left);
		}
		if (root.right != null) {
			recursiveFirstForeachBinaryTree(root.right);
		}
	}

	public void recursiveMiddleForeachBinaryTree(PracticeTreeNode root) {
		if (root == null) {
			return;
		}
		if (root.left != null) {
			recursiveFirstForeachBinaryTree(root.left);
		}
		System.out.println(root.val);
		if (root.right != null) {
			recursiveFirstForeachBinaryTree(root.right);
		}
	}

	public void recursiveAfterForeachBinaryTree(PracticeTreeNode root) {
		if (root == null) {
			return;
		}
		if (root.left != null) {
			recursiveFirstForeachBinaryTree(root.left);
		}
		if (root.right != null) {
			recursiveFirstForeachBinaryTree(root.right);
		}
		System.out.println(root.val);
	}

	public static void nonRecursiveForeachBinaryTree(PracticeTreeNode root) {
		if (root == null) {
			return;
		}
		Stack<PracticeTreeNode> stack = new Stack<>();
		stack.push(root);
		PracticeTreeNode node = root;
		while (true) {
			//如果栈为空表示迭代玩了
			if (stack.isEmpty()) {
				return;
			}
			//如果节点不为空
			if (node != null) {
				//打印父节点
				System.out.println(node.val);
				//右节点不为空则放到栈里面去
				if (node.right != null) {
					stack.push(node.right);
				}
				node = node.left;
			} else {
				node = stack.pop();
			}
		}
	}

	public static void nonRecursiveMiddleForeachBinaryTree(PracticeTreeNode root) {
		if (root == null) {
			return;
		}
		Stack<PracticeTreeNode> stack = new Stack<>();
		while (true) {
			if (root != null) {
				stack.push(root);
				root = root.left;
			} else if (stack.isEmpty()) {//如果栈为空表示迭代玩了
				return;
			} else {
				PracticeTreeNode node = stack.pop();
				System.out.println(node.val);
				if (node.right != null) {
					root = node.right;
				}
			}
		}
	}

	public static void nonRecursiveAfterForeachBinaryTree(PracticeTreeNode root){
		if (root == null) {
			return;
		}
		Stack<PracticeTreeNode> stack = new Stack<>();
		Stack<PracticeTreeNode> stack2 = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()){
			root = stack.pop();
			stack2.push(root);
			if (root.left!=null){
				stack.push(root.left);
			}
			if (root.right!=null){
				stack.push(root.right);
			}
		}
		while (!stack2.isEmpty()){
			System.out.println(stack2.pop().val);
		}
	}
}
